import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/19 20:09
 * @description 双栈，仅包含 + -
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.calculate("(1+(4+5+2)-3)+(6+8)");
    }
    public int calculate(String s) {
        // 存放所有的数字
        Deque<Integer> nums = new ArrayDeque<>();
        // 防止第一个负数，nums先加0
        nums.push(0);
        // 将所有的空格去掉
        s = s.replaceAll(" ", "");
        // 存放所有的操作
        Deque<Character> ops = new ArrayDeque<>();
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.push(c);
            }else if (c == ')') {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty()) {
                    char op = ops.peek();
                    if (op != '(') {
                        calc(nums, ops);
                    }else {
                        ops.pop();
                        break;
                    }
                }
            }else {
                if (isNumber(c)) {
                    int sum = 0;
                    int j = i;
                    while (j < n && isNumber(cs[j])) {
                        sum = sum * 10 + (cs[j] - '0');
                        j++;
                    }
                    nums.push(sum);
                    i = j - 1;
                }else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.push(0);
                    }
                    // 有一个新操作要入栈时，先把栈内计算
                    while (!ops.isEmpty() && ops.peek() != '(') {
                        calc(nums, ops);
                    }
                    ops.push(c);
                }
            }
        }
        while (!ops.isEmpty()) {
            calc(nums, ops);
        }
        return nums.peek();
    }

    public void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int b = nums.pop(), a = nums.pop();
        char op = ops.pop();
        nums.push(op == '+' ? a + b : a - b);
    }
    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}
